Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 11487 - Gathering Food / gathering.cpp
blob30972c7177161bb688c0eef32341ccf234a0b1ac
1 #include <iostream>
2 #include <queue>
3 using namespace std;
5 bool v[11][11][27];
6 int dp[11*11*27][11][11][27];
7 char g[11][11];
9 struct state{
10 int i, j, w;
11 char last;
12 state(){} state(int I, int J, char L, int W) : i(I), j(J), last(L), w(W) {}
15 int n;
16 char final;
17 int di[] = {-1, +1, +0, +0};
18 int dj[] = {+0, +0, +1, -1};
20 #define inside(i, j) (0 <= i && i < n && 0 <= j && j < n)
21 #define D(x) cout << #x " es " << x << endl
22 #define unchar(c) ((c)-'A')
24 const int mod = 20437;
26 void bfs(int si, int sj){
27 memset(v, 0, sizeof v);
28 memset(dp, 0, sizeof dp);
29 dp[0][si][sj][0] = 1;
31 queue<state> q;
32 q.push(state(si, sj, 'A', 0));
33 while (q.size()){
34 int i = q.front().i, j = q.front().j, w = q.front().w;
35 char last = q.front().last;
36 //printf("popped (%d, %d, %c, %d)\n", i, j, last, w);
37 q.pop();
38 if (v[i][j][unchar(last)]) continue;
39 v[i][j][unchar(last)] = true;
41 if (g[i][j] == final){
42 //Llegue
43 cout << w << " " << (dp[w][i][j][unchar(last)] % mod) << endl;
44 return;
46 int new_paths = dp[w][i][j][unchar(last)];
47 if (g[i][j] == last) g[i][j] = '.', last++;
48 //D(new_paths);
49 for (int k=0; k<4; ++k){
50 int ni = i + di[k], nj = j + dj[k];
51 if (inside(ni, nj) && !v[ni][nj][unchar(last)] && (g[ni][nj] == '.' || g[ni][nj] == last)){
52 dp[w+1][ni][nj][unchar(last)] = ((dp[w+1][ni][nj][unchar(last)])%mod + (new_paths)%mod)%mod;
53 q.push(state(ni, nj, last, w+1));
57 cout << "Impossible" << endl;
60 int main(){
61 int C=1;
62 while (cin >> n && n){
63 int si, sj;
64 final = 'A';
65 for (int i=0; i<n; ++i){
66 for (int j=0; j<n; ++j){
67 cin >> g[i][j];
68 if (g[i][j] == 'A') si = i, sj = j;
69 if (g[i][j] > final) final = g[i][j];
72 cout << "Case " << C++ << ": ";
73 bfs(si, sj);
75 return 0;